package com.test.pack1.demo.base2_3;

import edu.princeton.cs.algs4.StdRandom;
import com.test.pack1.demo.base2_1.Selection;

/**
 * Created by dws on 2018/2/26.
 * 快速排序法
 */
public class Quick {

    public static void main(String[] args) {
        Integer[] a = {23,32,323,423,1,321,2,23};
        sort(a);
        for (Integer o : a){
            System.out.println(o);
        }
    }

    public static void sort(Comparable[] a){
        StdRandom.shuffle(a);
        sort(a,0,a.length-1);
    }

    private static void sort(Comparable[] a ,int lo,int hi){
        if(hi<=lo)return;
        int j = partition(a,lo,hi);
        sort(a,lo,j-1);
        sort(a,j+1,hi);
    }

    private static int partition(Comparable[] a ,int lo,int hi){//将数组切分为a[lo..i-1],a[i],a[i+1..hi]
        int i= lo,j=hi+1;
        Comparable v = a[lo];
        while (true){
            while(less(a[++i],v))if(i==hi)break;
            while (less(v,a[--j]))if(j==lo)break;
            if(i>=j)break;
            Selection.exch(a,i,j);
        }
        Selection.exch(a,lo,j);
        return j;
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

}
